#define _CRT_SECURE_NO_WARNINGS
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* pre = NULL;
    struct ListNode* ptail1 = list1;
    struct ListNode* ptail2 = list2;
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    if (list1->val < list2->val)
    {
        pre = list1;
        ptail1 = ptail1->next;
    }
    else {
        pre = list2;
        ptail2 = ptail2->next;
    }
    struct ListNode* head = pre;
    while (ptail1 != NULL && ptail2 != NULL)
    {
        if (ptail1->val < ptail2->val)
        {
            pre->next = ptail1;
            pre = pre->next;
            ptail1 = ptail1->next;
        }
        else {
            pre->next = ptail2;
            pre = pre->next;
            ptail2 = ptail2->next;
        }

    }
    if (ptail1)
    {
        pre->next = ptail1;
    }
    if (ptail2)
        pre->next = ptail2;
    return head;


}